package com.zx._12_算法.排序;

import com.zx._12_算法.Arrs.IAS;
import com.zx._12_算法.Nums;

/**
 * @version v1.0
 * @Project: knowledge
 * @Title: Sort1
 * @Description: No.2 选择排序,或者叫做简单选择排序
 *         选择排序的思路是这样的：
 *         首先，找到数组中最小的元素，拎出来，将它和数组的第一个元素交换位置，
 *         第二步，在剩下的元素中继续寻找最小的元素，拎出来，和数组的第二个元素交换位置，如此循环，直到整个数组排序完成。
 *         至于选大还是选小，这个都无所谓，你也可以每次选择最大的拎出来排，也可以每次选择最小的拎出来的排，只要你的排序的手段是这种方式，都叫选择排序。
 *         双层循环，时间复杂度和冒泡一模一样，都是O(n^2)。
 * @author: zhangxue
 * @date: 2019年7月7日下午9:27:41
 * @company: 未知之地
 * @Copyright: Copyright (c) 2019
 */
public class Sort2_选择排序 implements IAS {

    @Override
    public void sort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            // 找到最小的值，放在i的位置
            int idx = i;
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] < nums[idx]) {
                    idx = j;
                    nums[idx] = nums[j];
                }
            }
            Nums.swap(nums, i, idx);

        }
    }
}
